Sortierung zusammenführen ist ein Sortieralgorithmus, der ein Array rekursiv in immer kleinere Unterarrays aufteilt, bis jedes Unterarray nur noch ein Element enthält. Die Subarrays werden dann in sortierter Reihenfolge zusammengeführt, beginnend mit den kleinsten Subarrays bis hin zum größten Subarray.
Hier ist ein Beispiel dafür, wie die Zusammenführungssortierung funktioniert. Beginnen wir mit dem folgenden Array:
„
[5, 3, 1, 2, 4]
„
Wir teilen das Array zunächst in zwei Unterarrays auf:
„
[5, 3]
[1, 2, 4]
„
Anschließend sortieren wir jedes Subarray rekursiv. Das erste Subarray ist bereits sortiert, sodass wir nichts tun müssen. Das zweite Subarray kann durch rekursive Aufteilung in zwei weitere Subarrays usw. sortiert werden.
Sobald die Subarrays sortiert sind, können wir sie in sortierter Reihenfolge zusammenführen. Wir beginnen mit dem Vergleich der ersten Elemente jedes Subarrays. Das kleinere Element wird dem sortierten Array hinzugefügt und das andere Element wird verworfen. Wir setzen diesen Vorgang fort, bis alle Elemente in beiden Unterarrays dem sortierten Array hinzugefügt wurden.
„
[1, 2, 3, 4, 5]
„
Der letzte Schritt besteht darin, das sortierte Array zurückzugeben.
Die Zusammenführungssortierung bietet gegenüber anderen Sortieralgorithmen eine Reihe von Vorteilen. Es wird garantiert, dass in O(n log n) Zeit ein sortiertes Array erstellt wird, unabhängig von der ursprünglichen Reihenfolge der Elemente im Array. Darüber hinaus ist die Zusammenführungssortierung stabil, was bedeutet, dass gleiche Elemente im sortierten Array in derselben Reihenfolge erscheinen, in der sie im ursprünglichen Array erschienen sind.
Hier ist eine detailliertere Erklärung des Merge-Sort-Algorithmus:
1. Teilen Sie das Array in zwei Unterarrays mit ungefähr gleicher Länge.
2. Sortieren Sie jedes Subarray rekursiv.
3. Führen Sie die beiden sortierten Unterarrays zu einem einzigen sortierten Array zusammen.
Der Zusammenführungsschritt ist der Schlüssel zur Zusammenführungssortierung. Es ist wichtig, die Subarrays in sortierter Reihenfolge zusammenzuführen. Dies kann durch Vergleichen der ersten Elemente jedes Subarrays und Hinzufügen des kleineren Elements zum sortierten Array erfolgen. Das andere Element wird verworfen. Dieser Vorgang wird wiederholt, bis alle Elemente in beiden Unterarrays dem sortierten Array hinzugefügt wurden.
Merge Sort ist ein leistungsstarker Sortieralgorithmus, der garantiert in O(n log n) Zeit ein sortiertes Array erzeugt. Es ist außerdem stabil und eignet sich daher zum Sortieren von Daten, die gleiche Elemente enthalten.
